package everydayone.LRUCache;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * @Date 2020/05/25
 * @author 王光浩
 * @Thinking 使用 HashMap+ArrayList；HashMap存储 key-value，用于get操作；ArrayList存储key用于
 * 			 put操作时当缓存已满删除最久未使用可以。
 * @Analysis get操作的时间复杂度O（n）；put操作的时间复杂度O（n）
 */
public class MyMethodOne {

	private HashMap<Integer, Integer> map; // 保存 key-value
	private ArrayList<Integer> arr; // 保存key最近使用的顺序
	private Integer capacity; // 保存最大容量

	public MyMethodOne(int capacity) {
		if (capacity <= 0)
			throw new RuntimeException("Capacity 不能小于等于0");

		map = new HashMap<Integer, Integer>(capacity * 4 / 3);
		arr = new ArrayList<Integer>(capacity);
		this.capacity = capacity;
	}

	/**
	 * 通过 map 来获取对应的 value，时间复杂度O（1）
	 * @param key the key
	 * @return	the value of the key mapping in map
	 */
	public int get(int key) {
		int ret = map.getOrDefault(key, -1);
		if ( ret != -1) 
			this.update(key);
		return ret;
	}
	
	/**
	 * 执行插入或更新操作
	 * @param key
	 * @param value
	 */
	public void put(int key, int value) {
		// 是插入元素
		if (map.put(key, value) == null) {
			// 需要删除最久未使用元素
			if (this.capacity == arr.size()) {
				map.remove(arr.get(0));
				arr.remove(0);
			}
			arr.add(key);
		// 更新元素
		} else {
			this.update(key);
		}
	}

	/**
	 * 将 key 从 arr 中移动到 arr 的末尾
	 * @param key
	 */
	public void update(int key) {
		if (arr.get(arr.size() - 1) != key) {
			// 查找 key 的下标
			for (int i = 0; i < arr.size() - 1; i++) {
				if (arr.get(i) == key) {
					arr.remove(i);
					break;
				}
			}
			arr.add(key);
		}
	}
}
